package 链表.链表相交_160;
/*
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，
它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。
这个例子的意思就是不要比较值，而是比较节点本身

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。
* */

public class Solution {
    static  ListNode[] head = new ListNode[4];
    static  ListNode[] headB = new ListNode[3];
    static  ListNode[] headA = new ListNode[4];
    public static void main(String[] args) {
        head[3] = new ListNode(4,null);
        head[2] = new ListNode(3,head[3]);
        head[1] = new ListNode(2,head[2]);
        head[0] = new ListNode(1,head[1]);

        headA[3] = new ListNode(4,null);
        headA[2] = new ListNode(3,headA[3]);
        headA[1] = new ListNode(2,headA[2]);
        headA[0] = new ListNode(1,headA[1]);

        headB[2] = new ListNode(4,null);
        headB[1] = new ListNode(3,headB[2]);
        headB[0] = new ListNode(1,headB[1]);
        ListNode answer = getIntersectionNode(head[0],headB[0]);
        if (answer == null){
            System.out.println("没有");
        }
        while (answer != null){
            System.out.println(answer.val);
            answer = answer.next;
        }
    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       /*
       ListNode curA = headA; ListNode curB = headB;
        int sizeA = 0, sizeB = 0;
        while (curA != null){
            curA = curA.next;
            sizeA ++;   // 计算A链表的长度
        }
        while (curB != null){
            curB = curB.next;
            sizeB ++;   // 计算B链表的长度
        }
        curA = headA;
        curB = headB;   // 将二者复原，重新指向表头
        int gap = Math.abs(sizeA - sizeB);
        if (sizeA < sizeB){
            ListNode temp = headA;
            curA = curB;
            curB = temp;
        }
        while (gap -- > 0){
            curA = curA.next;  // 移动至二者长度一致
        }

        while (curA != null){
            if (curA.val == curB.val){ // 自己测试的时候测试的是值，但是leetcode测试的是curA==curB
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        System.out.println("bbb");
        return null;*/
         int lenA = 0, lenB = 0;
         ListNode tempA = headA, tempB = headB;
         while (tempA != null){
             lenA ++;
             tempA = tempA.next;
         }
         while (tempB != null){
             lenB ++;
             tempB = tempB.next;
         }
         tempA = reverse(headA);
         tempB = reverse(headB);
         int shortVal = (lenA > lenB) ? lenB : lenA;
         ListNode ans = null;
         if (tempA.val != tempB.val){
             System.out.println("aaa");
             return null;
         }
         while (shortVal -- > 0){
             if (tempA.val == tempB.val){
                 ans = tempA;
                 tempA = tempA.next;
                 tempB = tempB.next;
             } else {
                 break;
             }
         }
         headA = reverse(tempA);
         
         return ans;
    }

    public static   ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = null;
        while (cur != null){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
    static class ListNode {
     int val;
     ListNode next;
    ListNode(int x) {
         val = x;
        next = null;
    }
        ListNode(int val, ListNode next) { this.val = val; this.next = next;
        }
 }
}

/*
           ListNode curA = headA; ListNode curB = headB;
            int sizeA = 0, sizeB = 0;
        while (curA != null){
            curA = curA.next;
            sizeA ++;   // 计算A链表的长度
        }
        while (curB != null){
            curB = curB.next;
            sizeB ++;   // 计算B链表的长度
        }
        curA = headA;
        curB = headB;   // 将二者复原，重新指向表头
        int gap = Math.abs(sizeA - sizeB);
        if (sizeA < sizeB){
            ListNode temp = headA;
            curA = curB;
            curB = temp;
        }
        while (gap -- > 0){
            curA = curA.next;  // 移动至二者长度一致
        }

        while (curA != null){
            if (curA == curB){ // 自己测试的时候测试的是值，但是leetcode测试的是curA==curB
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
* */